Damerau
Implements the Damerau-Levenshtein distance (Damerau, 1964) with transposition (also sometimes calls unrestricted Damerau-Levenshtein distance). It is the minimum number of operations needed to transform one string into the other, where an operation is defined as an insertion, deletion, or substitution of a single character, or a transposition of two adjacent characters. It does respect triangle inequality, and is thus a metric distance.
This is not to be confused with the optimal string alignment distance, which is an extension where no substring can be edited more than once.
The similarity is computed as \(\frac{w_d \lvert X \rvert + w_i \lvert Y \rvert - distance(X, Y)}{2}\).
References
Damerau, F. J. (1964-03). A technique for computer detection and correction of spelling errors. Communications of the ACM, 7(3), 171-176. https://doi.org/10.1145/363958.363994[sci-hub]
Author
solonovamax
Parameters
The weight of an insertion. Represented as \(w_i\). Must be in the range \([0, 1 \times 10^{10} ]\).
The weight of a deletion. Represented as \(w_d\). Must be in the range \([0, 1 \times 10^{10} ]\).
The weight of a substitution. Represented as \(w_s\). Must be in the range \([0, 1 \times 10^{10} ]\).
The weight of a substitution. Represented as \(w_t\). Must be in the range \([0, 1 \times 10^{10} ]\).
See also
Properties
The weight of a deletion. Represented as \(w_d\).
The weight of an insertion. Represented as \(w_i\).
The weight of a substitution. Represented as \(w_s\).
The weight of a transposition. Represented as \(w_t\).